package org.example.myleet.p472;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;

public class Solution {

    private List<String> result;

    private TrieTree trieTree;

    /**
     * 思路：排序+字典树+DFS
     * 考虑到连接词一定是由更短的单词连接（可以重复使用）得到，因此更短的单词更有可能是连接词的组成部分，因此排序可以让基础单词优先加入字典树
     * 字典树用于记忆出现过哪些单词属于非连接词，连接词不用加入字典树，因为连接词A如果是另一个连接词B的组成部分，
     * 则连接词A原来的组成部分也一定是连接词B的组成部分
     * 最后通过DFS遍历字典树的子树就可以找到一个匹配的组成部分，找到一个组成部分后则在下一个字符从字典树根开始继续遍历
     */
    public List<String> findAllConcatenatedWordsInADict(String[] words) {
        result = new ArrayList<>();
        trieTree = new TrieTree();
        //先排序
        Arrays.sort(words, new Comparator<String>() {
            @Override
            public int compare(String o1, String o2) {
                return o1.length() - o2.length();
            }
        });
        //加入第一个单词初始化，第一个单词一定不是连接词
        trieTree.addWord(words[0].toCharArray());
        for (int i = 1; i < words.length; ++i) {
            if (trieTree.isContainOtherWord(words[i].toCharArray(), 0, trieTree.root)) {
                //如果words[i]是连接词，则加入到结果中
                result.add(words[i]);
            } else {
                //如果words[i]不是连接词，则加入到字典树中
                trieTree.addWord(words[i].toCharArray());
            }
        }
        return result;
    }

    class TrieTree {
        public Trie[] root;

        public TrieTree() {
            root = new Trie[Trie.SUB_SIZE];
        }

        public void addWord(char[] wordChars) {
            if (wordChars.length < 1) {
                return;
            }
            char c = wordChars[0];
            int i_ = c - 'a';
            if (null == root[i_]) {
                root[i_] = new Trie(c);
            }
            addWordDfs(wordChars, 1, root[i_]);
        }

        private void addWordDfs(char[] wordChars, int i, Trie node) {
            if (i >= wordChars.length) {
                node.end = true;
                return;
            }
            char c = wordChars[i];
            Trie[] children = node.children;
            int i_ = c - 'a';
            if (null == children[i_]) {
                children[i_] = new Trie(c);
            }
            addWordDfs(wordChars, i + 1, children[i_]);
        }

        public boolean isContainOtherWord(char[] wordChars, int i, Trie[] children) {
            if (wordChars.length < 1) {
                return false;
            }
            char c = wordChars[i];
            int i_ = c - 'a';
            if (null == children[i_]) {
                return false;
            }
            if (children[i_].end) {
                //找到一个组成单词的结束
                if (i + 1 >= wordChars.length) {
                    //如果这个结束的位置也是wordChars的结束位置，相当于找到连接词了
                    return true;
                }
                if (isContainOtherWord(wordChars, i + 1, root)) {
                    //这个结束位置不是wordChars的结束位置，则从字典树顶开始重新寻找
                    return true;
                }
            }
            if (i + 1 >= wordChars.length) {
                //找到wordChars结尾了都没找到组成词，说明这个词不是连接词，结束
                return false;
            }
            //DFS
            return isContainOtherWord(wordChars, i + 1, children[i_].children);
        }
    }

    class Trie {

        public static final int SUB_SIZE = 26;

        public char c;

        public boolean end;

        public Trie[] children;

        public Trie(char c) {
            this.c = c;
            end = false;
            children = new Trie[SUB_SIZE];
        }
    }
}
